package cn.dapeng.bitmap;

/**
 * 使用位运算实现加、减、乘、除
 */
public class BitOperator {

    /**
     * 加法
     * 异或运算 是 无进位相加
     * <p>
     *   0110110
     * ^ 1110111
     * -----------------------
     *  1000001
     *
     * @param a
     * @param b
     * @return
     */
    public static int add(int a, int b) {
        // (a ^ b) + ((a & b) << 1)
        int sum = a;
        while (b != 0) {
            sum = a ^ b; // 先计算无进位相加的信息
            b = (a & b) << 1; // 再计算进位信息
            a = sum;
        }
        return sum;
    }

    /**
     * 相反数
     *
     * @param n
     * @return
     */
    public static int negNum(int n) {
        return add(~n, 1);
    }

    /**
     * 减法
     *
     * @param a
     * @param b
     * @return
     */
    public static int minus(int a, int b) {
        return add(a, negNum(b));
    }

    /**
     * 乘法
     *
     * @param a
     * @param b
     * @return
     */
    public static int multi(int a, int b) {
        int ans = 0;
        while (b != 0) {
            if ((b & 1) != 0) {
                ans = add(ans, a);
            }
            a <<= 1;
            b >>>= 1;
        }
        return ans;
    }

    /**
     * a和b都不是系统最小值的情况
     *
     * @param a
     * @param b
     * @return
     */
    public static int div(int a, int b) {

        int x = isNeg(a) ? negNum(a) : a;
        int y = isNeg(b) ? negNum(b) : b;
        int answer = 0;

        for (int i = 30; i >= 0; i = minus(i, 1)) {
            if ((x >> i) >= y) {
                answer |= (1 << i);
                x = minus(x, y << i);
            }
        }

        return answer;
    }

    /**
     * 考虑a和b有可能是系统最小值情况
     *
     * @param a
     * @param b
     * @return
     */
    public static int divide(int a, int b) {
        if (a == Integer.MIN_VALUE && b == Integer.MIN_VALUE) {
            return 1;
        } else if (b == Integer.MIN_VALUE) {
            return 0;
        } else if (a == Integer.MIN_VALUE) {
            if (b == negNum(1)) {
                return Integer.MAX_VALUE;
            } else {
                int ans = div(add(a, 1), b);
                return add(ans, div(minus(a, multi(ans, b)), b));
            }
        } else {
            div(a, b);
        }
        return 0;
    }

    /**
     * 判断数字是否负数
     *
     * @param n
     * @return
     */
    public static boolean isNeg(int n) {
        return n < 0;
    }

    public static void main(String[] args) {
        int testTimes = 10_0000, maxValue = 100000;
        for (int i = 0; i < testTimes; i++) {
            int a = (int) (Math.random() * maxValue);
            int b = (int) (Math.random() * maxValue) + 1;

            if (multi(a, b) != (a * b)) {
                System.out.println(a + "-" + b);
                System.out.println("Oops");
                break;
            }

            if (div(a, b) != (a / b)) {
                System.out.println(a + "-" + b);
                System.out.println("Oops");
                break;
            }
        }

        System.out.println(divide(Integer.MIN_VALUE, Integer.MIN_VALUE));
        System.out.println(divide(1, Integer.MIN_VALUE));

        System.out.println(divide(Integer.MIN_VALUE, -1));
        System.out.println(divide(Integer.MIN_VALUE, Integer.MIN_VALUE + 1));
    }

}
